package LinkedList;

public class LinkedList implements Define{
    public ListNode first;
    public ListNode last;   //last永远用来记录尾结点
    @Override
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(first==null) {
            first=last=node;
            return;
        }
        node.next=first;
        first.prev=node;
        first=node;
    }

    @Override
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(first==null) {
            first=last=node;
        }else {
            last.next=node;
            node.prev=last;
            last=node;
        }
    }
    private void checkIndex(int index) {
        if(index<0||index>size()) {
            throw new CheckIndexOutOfException("位置信息有误!!!");
        }
    }
    @Override
    public void addIndex(int pos, int data) {
        checkIndex(pos);
        ListNode node=new ListNode(data);
        int count=0;
        ListNode cur=first;
        if(pos==0) {
            addFirst(data);
            return;
        }
        if(pos==size()) {
            addLast(data);
            return;
        }
        while(cur!=null) {
            if ((count++) == pos) {
                cur.prev.next = node;
                node.prev = cur.prev;
                node.next = cur;
                cur.prev = node;
                break;
            }
            cur = cur.next;
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur=first;
        while(cur!=null) {
            if(cur.val==key) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public int removePos(int pos) {
        checkIndex(pos+1);
        ListNode cur=first;
        int count=0;
        while(cur!=null) {
            if(pos==0) {
                if(first.next==null) {       //如果只有一个结点时
                    first=null;
                    break;
                }
                first=first.next;
                first.prev=null;
                break;
            }else if((count++)==pos) {
                if(cur.next==null) {               //这里代表删除的是最后一个key结点
                    cur.prev.next=cur.next;
                    break;
                }
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                break;
            }
            cur=cur.next;
        }
        return cur.val;
    }
    @Override
    public void remove(int key) {
        ListNode cur=first;
        while(cur!=null) {
            if(first.val==key) {
                if(first.next==null) {       //如果只有一个结点时
                    first=null;
                    break;
                }
                first=first.next;
                first.prev=null;
                break;
            }else if(cur.val==key) {
                if(cur.next==null) {               //这里代表删除的是最后一个key结点
                    cur.prev.next=cur.next;
                    break;
                }
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                break;
            }
            cur=cur.next;
        }
    }

    @Override
    public void removeAll(int key) {
        ListNode cur=first;
        while(cur!=null) {
            if(first.val==key) {
                if(first.next==null) {       //如果只有一个结点时
                    first=null;
                    break;
                }
                first=first.next;
                first.prev=null;
            }else if(cur.val==key) {
                if(cur.next==null) {               //这里代表删除的是最后一个key结点
                    cur.prev.next=cur.next;
                    break;
                }
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
    }

    @Override
    public void display() {
        ListNode cur=first;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    public void display(ListNode node) {
        ListNode cur=node;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    @Override
    public int size() {
        int count=0;
        ListNode cur=first;
        while(cur!=null) {
            count++;
            cur=cur.next;
        }
        return count;
    }

    @Override
    public ListNode get(int pos) {
        checkIndex(pos);
        int count=0;
        ListNode cur=first;
        while(cur!=null) {
            if((count++)==pos) {
                break;
            }
            cur=cur.next;
        }
        if(cur==null) {
            return null;
        }
        return cur;
    }

    @Override
    public void clear() {
        ListNode cur=first;
        while(cur!=null) {              //每一个前驱后继都指向空
            ListNode next=cur.next;
            cur.prev=null;
            cur.next=null;
            cur=next;
        }
        first=last=null;                //此时再将first和last置为空，让整个链表彻底消失!!!
    }
}